package project2;

/*
* 2019-11-22
* 自底向上的归并排序需要1/2nlgn——nlgn次比较，最多6nlgn次"数组"访问(a、aux)
* 处理一个数组的遍数是lgn，每一遍访问6n次，比较1/2n——n次
* 1/2n次比较，考虑每次都是取一边的元素，然后剩下的一边依次进入
* */
public class BUM {
    public void sort(int[] a){
        Merge m = new Merge();
        int n = a.length;
        m.aux = new int[a.length];
        for(int size = 1; size < n; size+=size){
            for(int lo = 0; lo < n - size; lo += (size+size)) {//一次加两个size
                m.merge(a, lo, lo+size-1, Math.min(lo + size + size - 1, n - 1));
            }
        }
    }
}
